Measurement matrix construction is critically important to signal sampling and reconstruction for compressed sensing. From a practical point of view, deterministic construction of the measurement matrix is better than random construction. In this paper, we propose a novel deterministic method to construct a measurement matrix for compressed sensing, CS-FF (compressed sensing-finite field) algorithm. For this proposed algorithm, the constructed measurement matrix is from the finite field Quasi-cyclic Low Density Parity Check (QC-LDPC) code and thus it has quasi-cyclic structure. Furthermore, we construct three groups of measurement matrices. The first group matrices are the proposed matrix and other matrices including deterministic construction matrices and random construction matrices. The other two group matrices are both constructed by our method. We compare the recovery performance of these matrices. Simulation results demonstrate that the recovery performance of our matrix is superior to that of the other matrices. In addition, simulation results show that the compression ratio is an important parameter to analyse and predict the recovery performance of the proposed measurement matrix. Moreover, these matrices have less storage requirement than that of a random one, and they achieve a better trade-off between complexity and performance. Therefore, from practical perspective, the proposed scheme is hardware friendly and easily implemented, and it is suitable to compressed sensing for its quasi-cyclic structure and good recovery performance.

In this paper, we address the problem of projective template matching which aims to estimate parameters of projective transformation. Although homography can be estimated by combining key-point-based local features and RANSAC, it can hardly be solved with feature-less images or high outlier rate images. Estimating the projective transformation remains a difficult problem due to high-dimensionality and strong non-convexity. Our approach is to quantize the parameters of projective transformation with binary finite field and search for an appropriate solution as the final result over the discrete sampling set. The benefit is that we can avoid searching among a huge amount of potential candidates. Furthermore, in order to approximate the global optimum more efficiently, we develop a level-wise adaptive sampling (LAS) method under genetic algorithm framework. With LAS, the individuals are uniformly selected from each fitness level and the elite solution finally converges to the global optimum. In the experiment, we compare our method against the popular projective solution and systematically analyse our method. The result shows that our method can provide convincing performance and holds wider application scope.

Biphase periodic sequences having elements +1 or -1 with the two-level autocorrelation function are desirable in communications and radars. However, in case of the biphase orthogonal periodic sequences, Turyn has conjectured that there exist only sequences with period 4, i.e., there exist the circulant Hadamard matrices for order 4 only. In this paper, it is described that the conjecture is proved to be true by means of the isomorphic mapping, the Chinese remainder theorem, the linear algebra, etc.

The linear complexity of binary sequences plays a fundamental part in cryptography. In the paper, we construct more general forms of generalized cyclotomic binary sequences with period 2pm+1qn+1. Furthermore, we establish the formula of the linear complexity of proposed sequences. The results reveal that such sequences with period 2pm+1qn+1 have a good balance property and high linear complexity.

The MQ problem, which consists of solving a system of multivariate quadratic polynomials over a finite field, has attracted the attention of researchers for the development of public-key cryptosystems because (1) it is NP-complete, (2) there is no known polynomial-time algorithm for its solution, even in the quantum computational model, and (3) it enables cryptographic primitives of practical interest. In 2011, Sakumoto, Shirai and Hiwatari presented two new zero-knowledge identification protocols based exclusively on the MQ problem. The 3-pass identification protocol of Sakumoto et al. has impersonation probability 2/3. In this paper, we propose an improvement that reduces the impersonation probability to 1/2. The result is a protocol that reduces the total computation time, the total communication needed and requires a smaller number of rounds for the same security level. We also present a new extension that achieves an additional communication reduction with the use of some smaller hash commitments, but maintaining the same security level.

In several important applications, we often encounter with the computation of a Toeplitz matrix vector product (TMVP). In this work, we propose a k-way splitting method for a TMVP over any field F, which is a generalization of that over GF(2) presented by Hasan and Negre. Furthermore, as an application of the TMVP method over F, we present the first subquadratic space complexity multiplier over any finite field GF(pn) defined by an irreducible trinomial.

In the paper [4], the authors generalized the Cipolla-Lehmer method [2][5] for computing square roots in finite fields to the case of r-th roots with r prime, and compared it with the Adleman-Manders-Miller method [1] from the experimental point of view. In this paper, we compare these two methods from the theoretical point of view.

We determine the linear complexity of binary sequences derived from the polynomial quotient modulo p defined by $F(u)equiv rac{f(u)-f_p(u)}{p} ~(mod~ p), qquad 0 le F(u) le p-1,~uge 0,$ where fp(u)≡f(u) (mod p), for general polynomials $f(x)in mathbb{Z}[x]$. The linear complexity equals to one of the following values {p2-p,p2-p+1,p2-1,p2} if 2 is a primitive root modulo p2, depending on p≡1 or 3 modulo 4 and the number of solutions of f'(u)≡0 (mod) p, where f'(x) is the derivative of f(x). Furthermore, we extend the constructions to d-ary sequences for prime d|(p-1) and d being a primitive root modulo p2.

We propose a parallel pth powering method over an arbitrary finite field GF(pm). Using the proposed method, we present the explicit formulae for the computation of cubing over a ternary field GF(3m) which is defined by irreducible trinomials. We show that the field cubing computation for irreducible trinomials, which plays an important role in calculating pairing, can be implemented very efficiently.

The security of pairing-based cryptosystems is determined by the difficulty of solving the discrete logarithm problem (DLP) over certain types of finite fields. One of the most efficient algorithms for computing a pairing is the ηT pairing over supersingular curves on finite fields of characteristic 3. Indeed many high-speed implementations of this pairing have been reported, and it is an attractive candidate for practical deployment of pairing-based cryptosystems. Since the embedding degree of the ηT pairing is 6, we deal with the difficulty of solving a DLP over the finite field GF(36n), where the function field sieve (FFS) is known as the asymptotically fastest algorithm of solving it. Moreover, several efficient algorithms are employed for implementation of the FFS, such as the large prime variation. In this paper, we estimate the time complexity of solving the DLP for the extension degrees n=97, 163, 193, 239, 313, 353, and 509, when we use the improved FFS. To accomplish our aim, we present several new computable estimation formulas to compute the explicit number of special polynomials used in the improved FFS. Our estimation contributes to the evaluation for the key length of pairing-based cryptosystems using the ηT pairing.

We consider the computation of r-th roots in finite fields. For the computation of square roots (i.e., the case of r=2), there are two typical methods: the Tonelli-Shanks method [7],[10] and the Cipolla-Lehmer method [3],[5]. The former method can be extended to the case of r-th roots with r prime, which is called the Adleman-Manders-Miller method [1]. In this paper, we generalize the Cipolla-Lehmer method to the case of r-th roots in Fq with r prime satisfying r | q-1, and provide an efficient computational procedure of our method. Furthermore, we implement our method and the Adleman-Manders-Miller method, and compare the results.

In this paper, we derive a fast polynomial basis multiplier for GF(2m) defined by pentanomials xm+xk3+xk2+xk1+1 with 1 ≤ k1 < k2 < k3 ≤ m/2 using the presented method by Park and Chang. The proposed multiplier has the time delay TA+(2+⌈log2(m-1)⌉) TX or TA+(3+⌈log2(m-1)⌉) TX which is the lowest one compared with known multipliers for pentanomials except for special types, where TA and TX denote the delays of one AND gate and one XOR gate, respectively. On the other hand, its space complexity is very slightly greater than the best known results.

In this note we suggest a new parallelizable mode of operation for message authentication codes (MACs). The new MAC algorithm iterates a pseudo-random function (PRF) FK:{0,1}m → {0,1}n, where K is a key and m,n are positive integers such that m ≥ 2n. The new construction is an improvement over a sequential MAC algorithm presented at FSE2008, solving positively an open problem posed in the paper – the new mode is capable of fully parallel execution while achieving rate-1 efficiency and “full n-bit” security. Interestingly enough, PMAC-like parallel structure, rather than CBC-like serial iteration, has beneficial side effects on security. That is, the new construction is provided with a more straightforward security proof and with an even better (“-free”) security bound than the FSE 2008 construction.

In this letter, we present a general construction of sequence sets with low correlation zone, which is based on finite fields and the balance property of some functions. The construction is more flexible as far as the partition of parameters is concerned. A simple example is also given to interpret the construction.

In most software development environments, time, computing and human resources needed to perform the testing of a component is strictly limited. In order to deal with such situations, this paper proposes a method of creating the best possible test suite (covering the maximum number of 3-tuples) within a fixed number of test cases.

We define a family of 2e+1-periodic binary threshold sequences and a family of p2-periodic binary threshold sequences by using Carmichael quotients modulo 2e (e > 2) and 2p (p is an odd prime), respectively. These are extensions of the construction derived from Fermat quotients modulo an odd prime in our earlier work. We determine exact values of the linear complexity, which are larger than half of the period. For cryptographic purpose, the linear complexities of the sequences in this letter are of desired values.

This paper presents a novel technique to realize Karnin et al.'s (k,n)-threshold schemes over binary field extensions as a software. Our realization uses the matrix representation of finite fields and matrix-vector multiplications, and enables rapid operations in software implementation. The theoretical evaluation and computer simulation reveal that our realization of Karnin et al.'s scheme achieves much faster processing time than the ordinary symbol oriented realization of the scheme. Further, we show that our realization has comparable performance to the existing exclusive-OR-based fast schemes of Fujii et al. and Kurihara et al.

In this paper, we present a specific type of irreducible polynomial which is an irreducible m-term polynomial of degree m. Designing the parallel multiplier over GF(2m) by the quadrinomial obtained from this irreducible polynomial, its critical delay path is smaller than that of conventional multipliers for some degree m.

Some new generalized cyclotomic sequences defined by C. Ding and T. Helleseth are proven to exhibit a number of good randomness properties. In this paper, we determine the defining pairs of these sequences of length pm (p prime, m ≥ 2) with order two, then from which we obtain their trace representation. Thus their linear complexity can be derived using Key's method.

Pairing-based cryptography provides us many novel cryptographic applications such as ID-based cryptosystems and efficient broadcast encryptions. The security problems in ubiquitous sensor networks have been discussed in many papers, and pairing-based cryptography is a crucial technique to solve them. Due to the limited resources in the current sensor node, it is challenged to optimize the implementation of pairings on sensor nodes. In this paper we present an efficient implementation of pairing over MICAz, which is widely used as a sensor node for ubiquitous sensor network. We improved the speed of ηT pairing by using a new efficient multiplication specialized for ATmega128L, called the block comb method and several optimization techniques to save the number of data load/store operations. The timing of ηT pairing over GF(2239) achieves about 1.93 sec, which is the fastest implementation of pairing over MICAz to the best of our knowledge. From our dramatic improvement, we now have much high possibility to make pairing-based cryptography for ubiquitous sensor networks practical.